|
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order ''n'' with a self-loop at each vertex has cycle rank ''n''. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found use in sparse matrix computations (see ) and logic . ==Definition== The cycle rank ''r''(''G'') of a digraph ''G'' = (''V'', ''E'') is inductively defined as follows: * If ''G'' is acyclic, then ''r''(''G'') = 0. * If ''G'' is strongly connected and ''E'' is nonempty, then ::where G - v is the digraph resulting from deletion of vertex v and all edges beginning or ending at v. * If ''G'' is not strongly connected, then ''r''(''G'') is equal to the maximum cycle rank among all strongly connected components of ''G''. The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「cycle rank」の詳細全文を読む スポンサード リンク
|